package algorithms;

import java.util.ArrayList;
import algorithms.Algorithm;
import animationEngine.AnimationState;

/**
 * The Class BoyerMooreTestAlgorithm, this class creates all of the animation states required
 * to animate the Boyer Moore Algorithm.
 * 
 * @author Andrei Palade
 * @author David McBrierty
 * @author Garry Sharp
 * @author Hristo Georgiev
 * @author John Dennis
 * @author Marco Sarconi
 * @version 1.0.1
 */
public class BoyerMooreTestAlgorithm implements Algorithm {

	/** The animation states. */
	ArrayList<AnimationState> animationStates = new ArrayList<AnimationState>();
	
    /** An array of ASCII symbols to use when creating the skip table */
    private int [] p;
    
    /** The Constant NUM_ASCII_SYMBOLS. */
    public static final short NUM_ASCII_SYMBOLS = 128;
    
    
    /**
     * Gets the table.
     *
     * @return the table
     */
    public int [] getTable() {
    	return p;
    }
    
	/* (non-Javadoc)
	 * @see algorithms.Algorithm#getStates(java.lang.String, java.lang.String)
	 */
	public ArrayList<AnimationState> getStates(String text, String pattern) {
		//System.out.format("Text: %s\nPattern: %s\n", text, pattern);

		int m = pattern.length(); // length of pattern
		int n = text.length(); // length of text

		int sp = 0; // current starting position of string in text
		int i = m - 1; // current position in text
		int j = m - 1; // current position in string/pattern
		
		p = new int[NUM_ASCII_SYMBOLS];
		
		setUp(pattern, p, m); // set up the last occurrence in pattern table
		printTable(p);
		
		/*
		 * Create starting animation state AnimationState(int textIndex, int
		 * patternPosition, int pseudoCodeLine, int textCharacterHighlight, int
		 * patternCharacterHighlight, boolean matches)
		 */
		animationStates.add(new AnimationState(i, sp, 0, i, j, false));
		while (sp <= n-m && j >= 0) {
			animationStates.add(new AnimationState(i, sp, 1, i, j, false));
			if (text.charAt(i) == pattern.charAt(j)) { // current characters match
				animationStates.add(new AnimationState(i, sp, 2, i, j, true));
				i--; // move back in text
				animationStates.add(new AnimationState(i, sp, 3, i, j, true));
				j--; // move back in string
				animationStates.add(new AnimationState(i, sp, 4, i, j, false));
			}
			else { // current characters do not match
				animationStates.add(new AnimationState(i, sp, 8, i, j, false));
				if (p[(short) text.charAt(i)] < j && p[(short) text.charAt(i)] >= 0) {
					sp += j - p[(short) text.charAt(i)];
					animationStates.add(new AnimationState(i, sp, 9, i, j, false));
					i += m - 1 - p[(short) text.charAt(i)];
					j = m - 1;
					animationStates.add(new AnimationState(i, sp, 10, i, j, false));
				}
				else if (p[(short) text.charAt(i)] > j) {
					i += m - j;				
					sp++;
					animationStates.add(new AnimationState(i, sp, 13, i, j, false));
					j = m - 1;
					animationStates.add(new AnimationState(i, sp, 14, i, j, false));
				}
				else if (p[(short) text.charAt(i)] == -1) {
					i += m;
					sp += j + 1;
					animationStates.add(new AnimationState(i, sp, 17, i, j, false));
					j = m - 1;
					animationStates.add(new AnimationState(i, sp, 18, i, j, false));
				}
			}
		}
		if (j < 0) {
			animationStates.add(new AnimationState(i, sp, 22, i, j, false));
			animationStates.add(new AnimationState(i, sp, 23, i, j, false));
			//System.out.format("Pattern found at position %d!\n", sp);
		}
		else {
			animationStates.add(new AnimationState(i, sp, 23, i, j, false));
			animationStates.add(new AnimationState(i, sp, 24, i, j, false));
			//System.out.format("Pattern NOT found!\n");
		}

   		return this.animationStates;
	}
	
	
	/**
	 * Carry out the pre-processing required for the Boyer Moore Algorithm (ie construct the
	 * skip table).
	 *
	 * @param pattern the pattern being searched for
	 * @param p the alphabet of characters allowed
	 * @param m the m //TODO FIX THIS
	 */
	public static void setUp(String pattern, int [] p, int m) {
		for (int i = 0; i < NUM_ASCII_SYMBOLS; i++) {
			p[i] = -1;
			for (int j = 0; j < m; j++) {
				if ((char) i == pattern.charAt(j))
					p[i] = j; 
			}
		}
	}
	
	/**
	 * Prints the skip table.
	 *
	 * @param p the alphabet of characters available.
	 */
	public static void printTable(int [] p) {
		for (int i = 0; i < NUM_ASCII_SYMBOLS; i++) {
			if (p[i] != -1)
				System.out.format("p[\'%c\'] = %d (%d)\n",  (char) i, p[i], i);
		}
	}
	
	
}